﻿using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.GeneralizedCoinChange.QuantityAndSizeModeling
{
    public class SpaceSavingDynamicCoinChanger : IDynamicCoinChanger
    {
        private readonly IList<int> _values;
        private readonly int _n;
        private readonly IList<double> _weights;

        public SpaceSavingDynamicCoinChanger(IList<int> values, IList<double> weights = null)
        {
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0,_n).ToAlgoritmiaList();
        }

        #region Implementation of IDynamicCoinChanger

        public double Weight(int Q)
        {
            var current = new[] {0.0}.Concat(Enumerable.Repeat(double.PositiveInfinity, Q)).ToArray();
            var previous = new double[Q+1];

            for(int n = 1; n <= _n; n++)
            {
                var tmp = previous;
                previous = current;
                current = tmp;
                for(int q = 0; q <= Q; q++)
                {
                    current[q] =
                        Enumerable.Range(0, (q/_values[n - 1]) + 1).Select(
                            i => previous[q - i*_values[n - 1]] + i*_weights[n - 1]).Min();
                }
            }
            return current[Q];
        }

        #endregion
    }
      
}
